package cn.com.forever.array;
/*
    给出一个整数数组 和有序的整数数组 ，请将数组 合并到数组 中，变成一个有序的升序数组
    注意：
    1.可以假设 数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 和 ，的数组空间大小为 +
    2.不要返回合并的数组，返回是空的，将数组 的数据合并到里面就好了
    3.数组在[0,m-1]的范围也是有序的

    例1:
    A: [1,2,3,0,0,0]，m=3
    B: [2,5,6]，n=3
    合并过后A为:
    A: [1,2,2,3,5,6]
 */
public class MergeArray {
    public static void main(String[] args) {
        int[] array = {2,6,4,8,1,10,34,7,5,0,0,0,0,0,0,0,0,0};
        int[] array2 = {2,6,4,8,1,10,34,7,5};
        merge(array,9,array2,9);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+ " ");
        }
    }

    public static void merge(int A[], int m, int B[], int n) {
        for (int i = m,j = 0; i < m+n && j< n; i++,j++) {
            A[i] = B[j];
        }
        quicksort(A,0,A.length-1);
    }

    public static void quicksort(int[] arr,int low,int high){
        if(low >= high)
            return ;
        int i = low ;
        int j = high ;
        int key = arr[low];
        while(i < j){
            while(i < j && arr[j] > key)
                j--;
            if(i < j){
                arr[i] = arr[j];
                i++;
            }
            while(i < j && arr[i] < key){
                i++;
            }
            if(i < j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;
        quicksort(arr,low,i-1);
        quicksort(arr,i+1,high);
    }
}
